package com.wxg.algorithm.chapter06;

public class UnionFind {

    private int[] id;
    private int   count;

    public UnionFind( int n ) {
        count = n;
        id = new int[n];
        for ( int i = 0 ; i < n ; i ++ ){
            id[i] = i;
        }
    }

    public int find( int p ) {
        if( p >= 0 && p < count) {
            return id[p];
        }else {
            throw new RuntimeException("传入的参数不合法");
        }
    }

    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }

    public void union( int p , int q ) {

        int pId = find(p);
        int qId = find(q);

        if ( pId != qId ) {
            for ( int i = 0 ; i < count ; i ++){
                if ( id[i] == pId ) {
                    id[i] = qId;
                }
            }
        }
    }
}
